package morris

func IsBst(head *Node) bool {

	cur := head
	var mostRight *Node
	var pre *Node

	for cur != nil {
		mostRight = cur.Left
		if mostRight != nil {
			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			if mostRight.Right == nil {
				mostRight.Right = cur
				cur = cur.Left
				continue
			} else {
				mostRight.Right = nil
			}
		}
		if pre != nil && pre.Val.(int) > cur.Val.(int)  {
			return false
		}
		pre = cur
		cur = cur.Right
	}
	return true
}
